package oct2013;

public class PermutationSequence {
	static int[] f;
	static {
		f = new int[10];
		f[0] = 1;
		for (int i = 1; i < 10; ++i) {
			f[i] = f[i - 1] * i;
		}
	}

	public String getPermutation(int n, int k) {
		StringBuilder sb = new StringBuilder();
		k = (k - 1) % f[n];
		boolean[] used = new boolean[n];
		for (int i = 0; i < n; ++i) {
			int v = k / f[n - i - 1] + 1;
			int j = 0, cnt = 0;
			for (j = 0; j < n; ++j) {
				if (!used[j]) {
					cnt++;
				}
				if (cnt == v)
					break;
			}
			used[j] = true;
			sb.append(j + 1);
			k %= f[n - i - 1];
		}
		return sb.toString();
	}
}
